package com.wtgroup.demo.leetcode.q003_重复字符的最长子串;

import java.util.HashMap;
import java.util.Map;

public class Solution {

    /*
     * 无重复字符的最长子串
     *
     */

    public static void main(String[] args) {
        String s = "au";
        int res = new Solution().lengthOfLongestSubstring(s);
        System.out.println(res);

        // String[] ss = {"", " ", "abcabcbb", "bbbbb", "pwwkew"};
        // for (String s : ss) {
        //     int res = new Solution().lengthOfLongestSubstring(s);
        //     System.out.println(res);
        // }
    }

    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }

        Map<Character, Integer> tmp = new HashMap<>();
        int maxLen = 0;
        int len = s.length();
        for (int i = 0; i < len-maxLen; i++) {
            int j = i + tmp.size(); // j 也跳跃
            for (; j < len; j++) {
                char cur = s.charAt(j);
                Integer existIndex = tmp.get(cur);
                if (existIndex != null) {
                    maxLen = tmp.size() > maxLen ? tmp.size() : maxLen;
                    tmp = copyAdapt(tmp, existIndex);
                    tmp.put(cur, j); // 更新 value
                    i = existIndex;
                    break;
                } else {
                    tmp.put(cur, j);
                }
            }
        }

        return tmp.size() > maxLen ? tmp.size() : maxLen; // 没有遇到过重复, maxLen为0
    }

    // 留下 existIndex 及之后 (重复没有put进去)
    private Map<Character, Integer> copyAdapt(Map<Character, Integer> src, Integer existIndex) {
        Map<Character, Integer> copy = new HashMap<>();
        for (Map.Entry<Character, Integer> entry : src.entrySet()) {
            if (entry.getValue() >= existIndex) {
                copy.put(entry.getKey(), entry.getValue());
            }
        }
        return copy;
    }
}
